104.Maximum Depth of Binary Tree

題目：
求出二元樹的最大深度，也就是從根節點到最遠葉子節點的
最長路徑上的節點數量

範例：

• Example 1:
  Input: root = [3,9,20,null,null,15,7]
  Output: 3

• Example 2:
  Input: root = [1,null,2]
  Output: 2

—

想法：

• 使用 BFS 進行層級遍歷
• 先將根節點加入佇列，並設定初始深度為 0
• 當佇列不為空時，每次迭代代表一個層級，深度加 1
• 遍歷當前層的所有節點，將其子節點加入佇列
• 佇列清空後，返回計算出的最大深度

—

程式碼：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size(); // 當前層的節點數

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // 將子節點加入佇列
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            depth++; // 層數加 1
        }
            return depth;
    }
}

—

實際操作：

queue = [3]
depth = 0

STEP1 (處理第 1 層)：
size = 1
poll = 3 -> queue = []
enqueue 9, 20 -> queue = [9, 20]
depth = 1

STEP2 (處理第 2 層)：
size = 2
poll = 9 -> queue = [20] (9 無子節點)
poll = 20 -> queue = [] (enqueue 15,7 -> queue = [15, 7])
depth = 2

STEP3 (處理第 3 層)：
size = 2
poll = 15 -> queue = [7] (15 無子節點)
poll = 7 -> queue = [] (7 無子節點)
depth = 3

結束：queue 空，返回 depth = 3